home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / prog / graph / neg_cycle.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  1.1 KB  |  63 lines
  1. #include <LEDA/graph.h>
  2. #include <LEDA/graph_alg.h>
  3.  
  4.  
  5. main()
  6. {
  7.  
  8. GRAPH<int,int> G;
  9. node u;
  10. edge e;
  11.  
  12. test_graph(G);
  13.  
  14. edge_array<int>  cost(G,0);
  15. node_array<int>  dist(G,0);
  16. node_array<edge> pred(G,nil);
  17. node_array<int>  label(G,0);
  18.  
  19. int mi = read_int("min cost = ");
  20. int ma = read_int("max cost = ");
  21.  
  22. forall_edges(e,G) cost[e] = G[e] = random(mi,ma);
  23.  
  24. node s = G.first_node();
  25.  
  26. float T = used_time();
  27.  
  28. cout << "BELLMAN_FORD <int>  " << flush;
  29. bool b = BELLMAN_FORD(G,s,cost,dist,pred);
  30. cout << string("%6.2f sec  ",used_time(T)) << endl;
  31. newline;
  32.  
  33.  
  34. if (b == false)
  35.   { cout << "Negative cycle:" << endl;
  36.     int count = 1;
  37.     forall_nodes(u,G)
  38.     { if (label[u] == 0)
  39.        { while (label[u]==0)
  40.          { label[u]=count;
  41.            u=source(pred[u]);
  42.           }
  43.          if (label[u] == count)  // cycle found
  44.          { list<edge> cycle;
  45.            for(e=pred[u]; source(e)!=u; e=pred[source(e)]) cycle.push(e);
  46.            cycle.push(e);
  47.            forall(e,cycle)
  48.            { G.print_edge(e);
  49.              newline;
  50.             }
  51.            newline;
  52.           }
  53.         }
  54.       count++;
  55.      }
  56.    }
  57. else
  58.   cout << "No negativ cycle found" << endl;
  59.  
  60. return 0;
  61.  
  62. }
  63.